#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

void QuickSort(int* a, int left, int right)
{
    if (left >= right) return;

    int keyi = left;
    int begin = left, end = right;
    while (begin < end)
    {
        while (begin < end && a[end] >= a[keyi]) end--;
        while (begin < end && a[begin] <= a[keyi]) begin++;
        swap(a[begin], a[end]);
    }
    swap(a[keyi], a[begin]);
    keyi = begin;

    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

void _MergeSort(int* a, int* tmp, int left, int right)
{
    if (left >= right) return;

    int mid = (left + right) / 2;

    //[left,mid] [mid+1,right]
    _MergeSort(a, tmp, left, mid);
    _MergeSort(a, tmp, mid + 1, right);

    int begin1 = left, begin2 = mid + 1;
    int end1 = mid, end2 = right;
    int i = left;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++];
        else tmp[i++] = a[begin2++];
    }
    while (begin1 <= end1) tmp[i++] = a[begin1++];
    while (begin2 <= end2) tmp[i++] = a[begin2++];

    for (int j = left; j <= right; j++) a[j] = tmp[j];
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
        return;

    _MergeSort(a, tmp, 0, n - 1);

    free(tmp);
    tmp = NULL;
}

int main()
{
    int a[] = { 1,5,8,6,4,9,7,2,3 };

    QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
    MergeSort(a, sizeof(a) / sizeof(a[0]));

    return 0;
}